1. Field of the Invention
The present invention relates to a method and apparatus for registering a plurality of digital images at subpixel accuracy (an accuracy finer than the size of a pixel).
2. Background Art
When performing image processing of a digital image, it is desirable to register a plurality of digital images at a finer accuracy than the size of a pixel (subpixel accuracy). Conventional techniques for registering a plurality of images at subpixel accuracy can be roughly divided into three kinds. A first technique is a correlation function interpolation method represented by the technique of V. N. Dvorchenko (V. N. Dvorchenko: xe2x80x9cBounds on (deterministic) correlation functions with applications to registrationxe2x80x9d, IEEE Trans. Pattern. Anal. Mach. Intell., Vol. PAMI-5, No.2, pp.206-213, 1983) which involves performing curve fitting on inter-image cross-correlation functions and obtaining the coordinates of the maximum value points of the cross-correlation functions at subpixel accuracy. A second technique is a gray level value interpolation method represented by the technique of J. A. Parker et.al. (J. A. Parker, R. V. Kenyon, and D. E. Droxel: xe2x80x9cComparison of interpolating methods for image resamplingxe2x80x9d, IEEE Trans. Med. Imaging, Vol. MI-2, No.1, pp.31-39, 1983) which involves for the respective images to be compared, obtaining the gray level values between pixels for one image by interpolation, shifting the image by 1/N pixel units, performing template matching at the other image which is not shifted, and then obtaining the best matching coordinate to thereby obtain the misregistration at an accuracy of 1/N pixels. A third technique is one represented by the technique of T. S. Huang (T. S. Huang: xe2x80x9cImage Sequence Analysisxe2x80x9d, p.303, Springer-Verlag, 1981), being a difference method which involves; considering one image (image A) to be displaced from the other image (image B) in the X direction by an incremental distance Dx, and in the Y direction by an incremental distance Dy, subjecting the gray level value of the image B to a Taylor expansion for Dx and Dy and obtaining a first order simultaneous equation for Dx and Dy from the difference of the gray level values of the image A and the image B, and then solving this equation to obtain Dx and Dy. Hereunder is a detailed description of the difference method. The gray level values of the images to be compared are respectively represented by f (x, y), g (x, y), where g (x, y) is for where f (x, y) is displaced by (Dx, Dy), and can be represented by g (x, y)=f (x-Dx, y-Dy). If (Dx, Dy) is very small, then the difference I (x, y) between f (x, y) and g (x, y) can be represented by:                               I          ⁡                      (                          x              ,              y                        )                          =                                                            ∂                                  f                  ⁡                                      (                                          x                      ,                      y                                        )                                                                              ∂                x                                      ⁢                          xe2x80x83                        ⁢            Dx                    +                                                    ∂                                  f                  ⁡                                      (                                          x                      ,                      y                                        )                                                                              ∂                x                                      ⁢                          xe2x80x83                        ⁢            Dy                                              (        1        )            
Values of I (x, y) and the partial differentials values of f (x, y) are obtained for various coordinates, and simultaneous equations for (Dx, Dy) in the various coordinates are set up from equation (1). Then by solving these simultaneous equations, (Dx, Dy) being the amount of shift of the relative positions between the two images, are obtained.
With the gray level value interpolation method and the difference method, the ways of representation are different, however these are theoretically the same as the correlation function interpolation method which searches for the point where the cross-correlation function takes a maximum.
With the abovementioned conventional techniques however, the implicitly assumed conditions are that the images to be registered are completely identical images, and only the positions relative to each other are shifted. Therefore in the case where deformation or noise is added to the image, the assumed conditions collapse, with the likelihood of not being able to correctly obtain the misregistration amount. Hereunder examples are given to explain the situation where it is not possible to correctly obtain the misregistration amount with the conventional techniques.
FIG. 10A shows an example of an input image where the gray level value change of a sloping portion on the edge is comparatively gentle, while FIG. 10B shows an example of an input image where the gray level value change of a sloping portion on the edge is comparatively abrupt. The results for where these two input images are registered and superposed are shown in FIG. 10C. In the case where, as shown in FIG. 10A and FIG. 10B, there is only one edge in the image, and the edge profiles are different between the input images, attributable for example to the optical characteristics of the imaging device, then when the above mentioned conventional techniques are used, since as shown in FIG. 10C these are superposed so that the area of the parts which are not superposed becomes a minimum, the edge pair defined by the maximum value point of the first order differential cannot always be superposed. Consequently the misregistration amount cannot be correctly obtained.
FIG. 11A shows an example of an input image with a radius at a corner, that is, the curvature of the corner is comparatively small, while FIG. 11B shows an example of an input image with no radius at the corner, that is, the curvature of the corner is comparatively large. The result of registering and superposing these two input images so that the straight line edge portions coincide is shown in FIG. 11C. Moreover, the result of superposing so that the area of the portions which do not overlap each other is a minimum is shown in FIG. 11D. In the case where in this way, the shapes of the corners of the patterns differ, then with the conventional technique, since these are superposed so that the area of the portions which are not superposed are a minimum, these are superposed with a shift as shown in FIG. 11D rather than with the edge pair lying on top of each other as shown in FIG. 11C.
FIG. 12A shows an example of an input image with a texture on the pattern. FIG. 12B also shows an example of an input image with a texture on the pattern. Of significance is that with the input image of FIG. 12B the texture is positioned slightly towards the edge compared to the input image of FIG. 12A. The result of superposing these two input images so that the edge portions coincide is shown in FIG. 12C, while the result of superposing so that the textures on the patterns coincide is shown in FIG. 12D. In the case where, as with FIGS. 12A and 12B, there is a texture with undulations of subtle gray level values on the pattern, attributable to variations in sensitivity between the respective detection elements of the imaging device or to video jitter and the like due to start timing shift of the respective scanning lines, then there is the likelihood of superimposing with the edge pair slightly shifted as shown in FIG. 12D, rather than with the edge pair superposed as shown in FIG. 12C.
FIG. 13A shows an example of an input image with a texture due to slight periodic noise on the pattern. FIG. 13B also shows an example of an input image with a texture due to a slight periodic noise on the pattern, however, compared to the input image of FIG. 13A, the phase of the periodic noise is shifted slightly towards the edge. The result of superimposing these two input images so that the edge portions coincide is shown in FIG. 13C. The result of superimposing so that the textures due to the slight periodic noise on the patterns coincide is shown in FIG. 13D. In the case where, as shown in FIGS. 13A and 13B, there is a periodic noise having a frequency and an amplitude which is the same for both of the compared images, but the phases of the noise are slightly shifted between images, then the area of the non-coinciding portion for when the images are superposed as shown in FIG. 13D so that the edge pair are not coincidingly overlapped but the periodic noise pair are coincidingly overlapped, is smaller than the area of the non-coinciding portion for when the images are superposed as shown in FIG. 13C so that the edge pair are coincidingly overlapped but the periodic noise pair are not coincidingly overlapped. At this time if registration is made using the abovementioned conventional technique, then the registration becomes as shown in FIG. 13D. Hence accurate registration is not possible. Moreover, also in the case where one peak of the noise is so small that it cannot be known if there is periodic noise or not by viewing with the eye, if there are many of such peaks, the areas of the non-coinciding portions accumulate so that there is the likelihood of a registration error. As an example of such periodic noise, there is the lateral stripes and the like accompanying the non-uniformity of the gray level values between scanning lines, which can often be seen in an interlaced scanning video image.
It is an object of the present invention to provide a method and apparatus for registering images which can perform registration with good accuracy even in the case where an image which is to be registered is subjected to deformation due to influences of the characteristics of the imaging device or noise.
The method of registering images of the present invention detects relative misregistration between an input first image and second image, and involves: performing differentiation for each of the images, in a longitudinal direction and a transverse direction of each image, and generating a longitudinal differential image having absolute values of longitudinal differential values as pixel values, and a transverse differential image having absolute values of transverse differential values as pixel values; generating a complete differential image from the longitudinal differential image and the transverse differential image; obtaining longitudinal direction fitting ranges for the longitudinal differential image by scanning the pixel values in the longitudinal direction; obtaining transverse direction fitting ranges for the transverse differential image by scanning the pixel values in the transverse direction, and for each of the longitudinal fitting ranges on the longitudinal differential image, fitting a mono-peak function in the longitudinal direction, and obtaining the coordinate of the maximum value point separated into subpixel accuracy being an accuracy of less than one pixel, and pixel accuracy, and making this the respective subpixel accuracy longitudinal direction edge position and the pixel accuracy longitudinal direction edge position, and with the pixel corresponding to the pixel accuracy longitudinal direction edge position as the edge pixel, generating a longitudinal direction edge position image having the subpixel accuracy longitudinal direction edge position as the pixel value of this edge pixel, and for each of the transverse fitting ranges on the transverse differential image, fitting a mono-peak function in the transverse direction, and obtaining the coordinate of the maximum value point separated into subpixel accuracy being an accuracy of less than one pixel, and pixel accuracy, and making this the respective subpixel accuracy transverse direction edge position and the pixel accuracy transverse direction edge position, and with the pixel corresponding to the pixel accuracy transverse direction edge position as the edge pixel, generating a transverse direction edge position image having the subpixel accuracy transverse direction edge position as the pixel value of this edge pixel, then generating a longitudinal differential image, a transverse differential image, a complete differential image, a longitudinal direction edge position image, and a transverse direction edge position image, respectively corresponding to images of the longitudinal differential image, the transverse differential image, the complete differential image, the longitudinal direction edge position image, and the transverse direction edge position image, which have been to pre-assigned sizes, then for each of the complete differential images, performing registration at an accuracy of one pixel by template matching, of the complete differential image of the first image with respect to the complete differential image of the second image, and in accordance with the result of this registration, registering at an accuracy of one pixel the longitudinal differential image, the transverse differential image, the longitudinal direction edge position image, and the transverse direction edge position image of the first image, with respect to the longitudinal differential image, the transverse differential image, the longitudinal direction edge position image, and the transverse direction edge position image of the second image, and when the longitudinal direction edge position image of the first image is superimposed on the longitudinal direction edge position image of the second image in accordance with the results of the registration at an accuracy of one pixel, making the pixels of the longitudinal direction edge position image of the second image which come into register with the respective edge pixels on the longitudinal direction edge position image of the first image, reference edge pixels, and using the subpixel accuracy longitudinal direction edge position image to obtain the distance between edge pixels, and based on the distance, obtaining the corresponding candidate edge pixel group corresponding to the reference edge pixel, and repeatedly computing in the corresponding candidate edge pixel group, to obtain the corresponding candidate edge pixel group with respect to all of the edge pixels on the longitudinal direction edge position image, and when the transverse direction edge position image of the first image is superimposed on the transverse direction edge position image of the second image in accordance with the results of the registration at an accuracy of one pixel, making the pixels of the transverse direction edge position image of the second image which come into register with the respective edge pixels on the first transverse direction edge position image, reference edge pixels, and then using the subpixel accuracy transverse direction edge position image to obtain the distance between edge pixels, and based on the distance, obtaining the corresponding candidate edge pixel group corresponding to the reference edge pixel, and repeatedly computing in the corresponding candidate edge pixel group, to obtain the corresponding candidate edge pixel group with respect to all of the edge pixels on the transverse direction edge position image, then fitting the subpixel accuracy edge positions of the respective edge pixels of the corresponding candidate edge pixel group with a curve described by a pre-assigned function shape and making this the corresponding candidate curve, and performing coordinate conversion so that the subpixel accuracy edge position of the reference edge pixel becomes the origin, and making the corresponding candidate curve in this coordinate system a relative corresponding candidate curve, and obtaining relative corresponding candidate curves for all of the longitudinal direction edge position images and the transverse direction edge position images, and for all of the edge pixels of the first image, plotting in one plane the respectively corresponding relative corresponding candidate curves of the second image, and obtaining at subpixel accuracy a point where all of the relative corresponding candidate curves intersect, or a point where all of the relative corresponding candidate curves are most concentrated, and making this a corresponding candidate intersection point, and then computing a displacement vector being a vector connecting from the origin of the coordinate system of the plotted plane to the corresponding candidate intersection point.
The apparatus for registering images of the present invention detects relative misregistration between an input first image and second image, and has: an image differentiating device for performing differentiation for each of the images, in a longitudinal direction and a transverse direction of each image, and generating a longitudinal differential image having absolute values of longitudinal differential values as pixel values, and a transverse differential image having absolute values of transverse differential values as pixel values, and generating a complete differential image from the longitudinal differential image and the transverse differential image; a fitting range setting device for obtaining longitudinal direction fitting ranges for the longitudinal differential image by scanning the pixel values in the longitudinal direction, and obtaining transverse direction fitting ranges for the transverse differential image by scanning the pixel values in the transverse direction; a function fitting device for fitting for each of the longitudinal fitting ranges on the longitudinal differential image, a mono-peak function in the longitudinal direction, and obtaining the coordinate of the maximum value point separated into subpixel accuracy being an accuracy of less than one pixel, and pixel accuracy, and making this the respective subpixel accuracy longitudinal direction edge position and the pixel accuracy longitudinal direction edge position, and with the pixel corresponding to the pixel accuracy longitudinal direction edge position as the edge pixel, generating a longitudinal direction edge position image having the subpixel accuracy longitudinal direction edge position as the pixel value of this edge pixel, and for each of the transverse fitting ranges on the transverse differential image, fitting a mono-peak function in the transverse direction, and obtaining the coordinate of the maximum value point separated into subpixel accuracy being an accuracy of less than one pixel, and pixel accuracy, and making this the respective subpixel accuracy transverse direction edge position and the pixel accuracy transverse direction edge position, and with the pixel corresponding to the pixel accuracy transverse direction edge position as the edge pixel, generating a transverse direction edge position image having the subpixel accuracy transverse direction edge position as the pixel value of this edge pixel; an image partitioning device for generating a longitudinal differential image, a transverse differential image, a complete differential image, a longitudinal direction edge position image, and a transverse direction edge position image, respectively corresponding to images of the longitudinal differential image, the transverse differential image, the complete differential image, the longitudinal direction edge position image, and the transverse direction edge position image, which have been to pre-assigned sizes; a pixel accuracy registration device for performing registration, for each of the complete differential images at an accuracy of one pixel by template matching, of the complete differential image of the first image with respect to the complete differential image of the second image, and in accordance with the result of this registration, registering at an accuracy of one pixel the longitudinal differential image, the transverse differential image, the longitudinal direction edge position image, and the transverse direction edge position image of the first image, with respect to the longitudinal differential image, the transverse differential image, the longitudinal direction edge position image, and the transverse direction edge position image of the second image; an edge correspondence affixing device for making, when the longitudinal direction edge position image of the first image is superimposed on the longitudinal direction edge position image of the second image in accordance with the results of registration by the pixel accuracy registration device, the pixels of the longitudinal direction edge position image of the second image which come into register with the respective edge pixels on the first longitudinal direction edge position image, reference edge pixels, and using the subpixel accuracy longitudinal direction edge position image to obtain the distance between edge pixels, and based on the distance, obtaining the corresponding candidate edge pixel group corresponding to the reference edge pixel, and repeatedly computing in the corresponding candidate edge pixel group, to obtain the corresponding candidate edge pixel group with respect to all of the edge pixels on the longitudinal direction edge position image, and when the transverse direction edge position image of the first image is superimposed on the transverse direction edge position image of the second image in accordance with the results of registration by the pixel accuracy registration device, making the pixels of the transverse direction edge position image of the second image which come into register with the respective edge pixels on the first transverse direction edge position image, reference edge pixels, and then using the subpixel accuracy transverse direction edge position image to obtain the distance between edge pixels, and based on the distance, obtaining the corresponding candidate edge pixel group corresponding to the reference edge pixel, and repeatedly computing in the corresponding candidate edge pixel group, to obtain the corresponding candidate edge pixel group with respect to all of the edge pixels on the transverse direction edge position image; a corresponding candidate curve generating device for fitting the subpixel accuracy edge positions of the respective edge pixels of the corresponding candidate edge pixel group with a curve described by a pre-assigned function shape and making this the corresponding candidate curve, and performing coordinate conversion so that the subpixel accuracy edge position of the reference edge pixel becomes the origin, and making the corresponding candidate curve in this coordinate system a relative corresponding candidate curve, and obtaining relative corresponding candidate curves for all of the longitudinal direction edge position images and the transverse direction edge position images; and a misregistration computing device for plotting in one plane for all of the edge pixels of the first image, the respectively corresponding relative corresponding candidate curves of the second image, and obtaining at subpixel accuracy a point where all of the relative corresponding candidate curves intersect, or a point where all of the relative corresponding candidate curves are most concentrated, and making this a corresponding candidate intersection point, and then computing a displacement vector being a vector connecting from the origin of the coordinate system of the plotted plane to the corresponding candidate intersection point.
With the present invention, the edge position of the pattern on the image which is not easily influenced by differences in edge profiles between images, or subtle textures, is obtained at subpixel accuracy by function fitting. Then based on this edge position, the distance between the corresponding edges of the images to be registered is obtained at subpixel accuracy, thereby obtaining the misregistration between images at subpixel accuracy. Moreover, by being able to set a threshold value which excludes the weak edge, then there is minimal susceptibility to noise.